/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode g1(-1), g2(-1), g(-1), *tail;
        g1.next=l1;
        g2.next=l2;
        tail=&g;
        while (g1.next!=NULL || g2.next!=NULL) {
            ListNode *cur;
            if (g2.next==NULL || (g1.next!=NULL && g1.next->val<g2.next->val)) {
                cur=g1.next;
                g1.next=g1.next->next;
            } else {
                cur=g2.next;
                g2.next=g2.next->next;
            }
            tail->next=cur;
            tail=cur;
            tail->next=NULL;
        }
        return g.next;
    }
};
